#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<stack>
#include<queue>
using namespace std;

#include"stack.h"

void test1()
{
    cx::stack<int, vector<int>> s;
    s.push(1);
    s.push(2);
    s.push(3);
    s.push(4);

    while (!s.empty())
    {
        cout << s.top() << ' ';
        s.pop();
    }
    cout << endl;
}

class MinStack {
public:
    void push(int val) {
        _s.push(val);

        if (_mins.empty() || _s.top() <= _mins.top())
        {
            _mins.push(val);
        }

    }
    void pop() {
        if (_s.top() == _mins.top())
        {
            _mins.pop();
        }
        _s.pop();

    }
    int top() {
        return _s.top();
    }
    int getMin() {
        return _mins.top();
    }
private:
    stack<int> _s;
    stack<int> _mins;

};


void test2()
{
    MinStack m;
}


class MyQueue {
public:
    MyQueue() {

    }

    void push(int x) {
        _pushs.push(x);
    }

    int pop() {
        if (_pops.empty())
        {
            while (!_pushs.empty())
            {
                _pops.push(_pushs.top());
                _pushs.pop();
            }
        }
        int top = _pops.top();
        _pops.pop();
        return top;
    }

    int peek() {
        if (_pops.empty())
        {
            while (!_pushs.empty())
            {
                _pops.push(_pushs.top());
                _pushs.pop();
            }
        }
        return _pops.top();
    }

    bool empty() {
        return _pushs.empty() && _pops.empty();
    }
private:
    stack<int> _pushs;
    stack<int> _pops;

};





class MyStack {
public:
    MyStack() {

    }

    void push(int x) {
        if (_q1.empty())
        {
            _q2.push(x);
        }
        else
        {
            _q1.push(x);
        }
    }

    int pop() {
        if (_q1.empty())
        {
            while (_q2.size() != 1)
            {
                _q1.push(_q2.front());
                _q2.pop();
            }
            int top = _q2.front();
            _q2.pop();
            return top;
        }
        else
        {
            while (_q1.size() != 1)
            {
                _q2.push(_q1.front());
                _q1.pop();
            }
            int top = _q1.front();
            _q1.pop();
            return top;
        }
    }

    int top() {
        if (_q1.empty())
        {
            while (_q2.size() != 1)
            {
                _q1.push(_q2.front());
                _q2.pop();
            }
            int top = _q2.front();
            _q1.push(_q2.front());
            _q2.pop();
            return top;
        }
        else
        {
            while (_q1.size() != 1)
            {
                _q2.push(_q1.front());
                _q1.pop();
            }
            int top = _q1.front();
            _q2.push(_q1.front());
            _q1.pop();
            return top;
        }
    }

    bool empty() {
        return _q1.empty() && _q2.empty();
    }
private:
    queue<int> _q1;
    queue<int> _q2;

};

void test3()
{
    MyStack s1;
    s1.push(1);
    s1.push(2);
    cout << s1.top() << endl;
    cout << s1.pop() << endl;
    cout << s1.empty() << endl;
}


class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> s;

        for (auto e : tokens)
        {
            if (e == "+")
            {
                int num1 = s.top();
                s.pop();
                int num2 = s.top();
                s.pop();

                s.push(num1 + num2);

            }
            else if (e == "-")
            {
                int num1 = s.top();
                s.pop();
                int num2 = s.top();
                s.pop();

                s.push(num2 - num1);
            }
            else if (e == "*")
            {
                int num1 = s.top();
                s.pop();
                int num2 = s.top();
                s.pop();

                s.push(num1 * num2);
            }
            else if (e == "/")
            {
                int num1 = s.top();
                s.pop();
                int num2 = s.top();
                s.pop();
                
                s.push(num2 / num1);


            }
            else
            {
                int num = 0;
                int flag = 1;
                for (auto e1 : e)
                {
                    if (e1 == '-')
                    {
                        flag = -1;
                        continue;
                    }
                    num *= 10;
                    num += e1 - '0';
                }
                s.push(num * flag);
            }

        }
        return s.top();
    }
};


void test4()
{
    vector<string> s = { "4","-2","/","2","-3","-","-" };
    cout << Solution().evalRPN(s) << endl;
}

int main()
{
    test1();
	return 0;
}